/**
 * @author haixuanwo
 * @email haixuanwo_clark@hotmail.com
 * @date 2021-09-24
 * @brief 实现KMP算法
 */

#include <iostream>
#include <string.h>
#include "01_KMP.h"

using namespace std;

int txhKMP::strStr(const char *mainStr, const char *subStr)
{
    if (nullptr == mainStr || nullptr == subStr)
    {
        std::cout<<"the para is nullptr"<<std::endl;
        return -1;
    }

    int subStrLen = strlen(subStr);
    int mainStrLen = strlen(mainStr);

    if (subStrLen <= 0 ||  mainStrLen <= 0 || mainStrLen < subStrLen)
    {
        std::cout<<"the subStrLen["<<subStrLen<<"] mainStrLen["<<mainStrLen<<"] error\n"<<std::endl;
        return -1;
    }

    if (false == getNext(subStr))
    {
        std::cout<<"getNext fail\n"<<std::endl;
        return -1;
    }

    int subStrIndex = 0;
    for (int i = 0; i <= mainStrLen; i++)
    {
        while (1)
        {
            // 字符不匹配
            if (mainStr[i]  != subStr[subStrIndex])
            {
                if (subStrIndex <= 0)
                {
                    break;
                }

                subStrIndex = next[subStrIndex - 1];
            }
            // 字符匹配
            else
            {
                subStrIndex++;
                if (subStrIndex == subStrLen)
                {
                    return (i - subStrLen + 1);
                }
                break;
            }
        }
    }

    return -1;
}

/**
 * @brief 获取next数组，即前缀列表。前缀和后缀的最大相等长度
 * @param subStr 子字符串
 * @return true成功，false失败
 */
bool txhKMP::getNext(const char *subStr)
{
    if (nullptr == subStr)
        return false;

    int subStrLen = strlen(subStr);
    if (subStrLen <= 0)
        return false;

    next  = new int[subStrLen];
    next[0] = 0;

    int indexPrefix = 1;
    int indexSuffix = 0;

    for (indexPrefix = 1; indexPrefix < subStrLen; indexPrefix++)
    {
        /**
         *  1、从最大匹配长度开始
         *  2、不相等则从next中获取上次的结果，继续匹配
         *  3、匹配成功则长度加一
         *  4、将最终的匹配长度赋值给next
         */
        while((indexSuffix > 0) && (subStr[indexPrefix] != subStr[indexSuffix]))
        {
            indexSuffix = next[indexSuffix - 1];
        }

        if (subStr[indexPrefix] == subStr[indexSuffix])
        {
            indexSuffix++;
        }

        next[indexPrefix] = indexSuffix;
    }

    showNext(subStr);

    return true;
}

void txhKMP::showNext(const char *subStr)
{
    int len = strlen(subStr);
    std::cout<<subStr<<"-len["<<len<<"]: ";

    for(int i = 0; i < len; i++)
    {
        std::cout<<next[i]<<" ";
    }
    std::cout<<std::endl;
}

#if 0
// 直接使用前缀表
class Solution {
public:
    // 获取next数组
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++)
        {
            // j要保证大于0，因为下面有取j-1作为数组下表的操作
            while (j > 0 && s[i] != s[j])
            {
                j = next[j - 1]; // 从j-1对应的回退值开始回退
            }

            if (s[i] == s[j])
            {
                j++;
            }
            next[i] = j;
        }
    }

    // 利用next数组进行匹配
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1]; // 这里要找j前一位的对应的回退位置了
            }

            if (haystack[i] == needle[j]) {
                j++;
            }

            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};



class KMP{
public:
    int strStr(string &mainStr, string &subStr)
    {
        int mainStrLen = mainStr.size();
        int subStrLen = subStr.size();

        if (0 == subStrLen) {
            return 0;
        }

        getNextArr(subStr);

        int j = 0;
        for (int i = 0; i < mainStrLen; i++) {
            while(j > 0 && mainStr[i] != subStr[j]) {
                j = next[j - 1]; // 这里要找j前一位的对应的回退位置了
            }

            if (mainStr[i] == subStr[j]) {
                j++;
            }

            if (j == subStrLen ) {
                return (i - subStrLen + 1);
            }
        }
        return -1;
    }

private:
    bool getNextArr(string &str)
    {
        int prefixIndex = 1; // 前缀末尾
        int suffixIndex = 0; // 后缀末尾
        int strLen = str.size();

        next.clear();
        next.push_back(0);   // next数组第一个元素为0

        for (prefixIndex = 1; prefixIndex < strLen; prefixIndex++)
        {
            //
            while(suffixIndex > 0 && str[suffixIndex] != str[prefixIndex])
                suffixIndex = next[suffixIndex - 1];

            if (str[suffixIndex] == str[prefixIndex])
                suffixIndex++;

            next.push_back(suffixIndex);
        }
        return 0;
    }

private:
    vector<int> next;
};

int main()
{
    string mainStr = "tanxiaohai";
    string subStr = "xiao";

    KMP kmp;
    cout<<kmp.strStr(mainStr, subStr)<<endl;

    return 0;
}
#endif

